package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 11. 旋转数组的最小数字
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。
 * 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
 * 示例 1：
 *
 * 输入：[3,4,5,1,2]
 * 输出：1
 * 示例 2：
 *
 * 输入：[2,2,2,0,1]
 * 输出：0
 * */
public class MinArray {
    /**
     * 方法：二分查找定位旋转起点
     * 思路：
     *        传统意义上认为，二分查找只能用在有序数组中，但其实二分查找法的核心思想在于减治。
     *        只要是可以减治的，那么都可以的用二分查找的。
     * 详解参考：语雀  https://www.yuque.com/jinyewuyou/rvn5p3/pm5sxv
     * */
    public int minArray(int[] numbers) {
        int left =0;
        int right = numbers.length -1;
        while(left <= right){
            int mid = left + (right -left)/2;
            if(numbers[mid] < numbers[right]){
                right = mid;
            }else if(numbers[mid] > numbers[right]){
                left= mid +1;
            }else{
                right--;
            }
        }
        return numbers[left];
    }

    public static void main(String[] args) {

    }
}
